package Hot_100;

public class T75_sortColors {
    public void sortColors(int[] nums) { //对数组进行原地修改，时间复杂度为O(n),空间复杂度为O(1)
        int len = nums.length;
        if (len < 2) {
            return;
        }
        int p0 = -1;
        int i = 0;
        int p2 = len;

//      [0,p0] -> 0
//      [p0,i] -> 1
//      [p2,len-1] -> 2
        while (i < p2) { //当i==p2时三个子区间都覆盖完整个数组了，循环终止
            if (nums[i] == 0) {
                p0++;
                swap(nums, i, p0); //交换完成之后i所指向的元素就是0，所以i++
                i++;
            } else if (nums[i] == 1) {
                i++;
            }else {
                p2--;
                swap(nums, i, p2); //i将2交换到p2的位置，但p2处的值未知，所以这里没有i++
            }
        }
    }

    void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
